package com.company.bytedance;

import java.util.Arrays;

public class QuickSort {
    public static void main(String[] args) {
        //Scanner in = new Scanner(System.in);
        //int a = in.nextInt();
        //System.out.println(a);
//        System.out.println("Hello World!");
        int[] array = {8,6,3,0,-1,-2};
        int[] array2 = {4,98,3,-94,23,-487,321,423,-724387};
        int[] array3 = {8,6,4,2,-1,-90};
        quickSort(array,0,array.length - 1);
        quickSort(array2,0,array2.length - 1);
        quickSort(array3,0,array3.length - 1);
        System.out.println(Arrays.toString(array));
        System.out.println(Arrays.toString(array2));
        System.out.println(Arrays.toString(array3));

    }

    private static void quickSort(int[] array,int left,int right){
        if(left >= right){
            return;
        }
        int pos = partition(array,left,right);
        quickSort(array,left,pos - 1);
        quickSort(array,pos + 1,right);

    }


    private static int partition(int[] array,int left,int right){

        int l = left;
        int r = right;
        int pivot = array[l];
        while(l < r){
            while(l < r && array[r] > pivot){
                r--;
            }
            array[l] = array[r];
            while(l < r && array[l] < pivot){
                l++;
            }
            array[r] = array[l];
        }
        array[l] = pivot;
        return l;

    }
}
